package main

import (
	"fmt"
	"sort"
)

func main() {
	sum := threeSum([]int{-1, 0, 1, 2, -1, -4})
	for _, ints := range sum {
		for i := range ints {
			fmt.Print(ints[i], " ")
		}
		fmt.Println()
	}

}

func threeSum(nums []int) [][]int {
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	res := make([][]int, 0)
	for i := 0; i < len(nums)-1; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		target := 0 - nums[i]
		isTarget := findSumIsTarget(nums[i+1:], target)
		if len(isTarget) > 0 {
			for _, idx := range isTarget {
				res = append(res, []int{nums[i], idx[0], idx[1]})
			}
		}
	}
	return res
}

func findSumIsTarget(nums []int, target int) [][2]int {
	result := make([][2]int, 0)
	j := len(nums) - 1
	i := 0
	for i < j {
		if nums[i]+nums[j] == target {
			result = append(result, [2]int{nums[i], nums[j]})
			i++
		} else if nums[i]+nums[j] < target {
			i++
		} else {
			j--
		}
	}
	return result
}
